<!DOCTYPE html>

<html>
<head>
    <meta charset="utf-8" />
    <title>TopCoder SRM 144 - 550: BinaryCode</title>
    
    <link type="image/x-icon" rel="shortcut icon" href="http://www.topcoder.com/i/favicon.ico"/>
    

    
    <style type="text/css">
        /* font */
body {
    font-family: Helvetica, Arial, Verdana, sans-serif;
    font-size: 16px;
    line-height: 1.2em;
}
ul.constraints > li:before, ul.notes > li:before {
    font-family: monospace;
    font-weight: normal;
}
.heading {
    font-weight: bold;
    font-size: 175%;
    line-height: 1.2em;
}
.section .section-title {
    font-weight: bold;
    font-size: 125%;
}
ol.testcases > li:before {
    font-family: monospace;
}
type {
    font-weight: bold;
    font-family: monospace;
}
li.testcase .data {
    font-family: monospace;
    line-height: 1.5em;
}

/* layout */
.heading {
    margin-top: 0.1em;
    margin-bottom:0.1em;
    text-align: center;
}
.section .section-title {
    margin-top : 1em;
    margin-bottom: 1em;
}
.problem-intro, note, user-constraint {
    padding-left: 1.25em;
}

/* Lists */
ul.constraints, ul.notes, ul.variables, ul.problem-definition-lines {
    list-style-type: none;
    padding: 0px;
}
ul.constraints > li:before {
    content: "-";
    position:relative;
    margin-left: 0px; /* optional, for multiline li element */
    left: 0.625em;
}
ul.notes > li:before {
    content: "-";
    position:relative;
    margin-left: 0px; /* optional, for multiline li element */
    left: 0.625em;
}

/* Testcases */
li.testcase {
    line-height: 1.1em;
    padding-top: 0.625em;
    padding-bottom: 0.625em;
    overflow: auto;
}
li.testcase > .testcase-content > div { padding-bottom: 0.5em; padding-left: 1em; }

li.testcase .testcase-comment {
    margin: 0;
    padding-left: 1em;
}
.testcase-comment p:first-child { margin-top: 0; }
.testcase-comment p:last-child { margin-bottom: 0; }

li.testcase .testcase-content {
    margin: 0.31em;
}

/* Data and variables */
.testcase-output {
    padding: 0.2em 1em 0.2em 0em;
}
.variables, .testcase-output {
    margin-left: 0.5em;
    display: table;
    margin-bottom: 0px;
    margin-top: 0px;
}
.variable {
    display: table-row;
}
.variable .name {
    padding: 0.2em 0em 0.2em 1em;
    font-weight: bold;
    display: table-cell;
    text-align: right;
}
.testcase-output .prefix {
    padding: 0.2em 0em 0.2em 1em;
    display: table-cell;
}
.testcase-output .prefix:after {
    content : ":";
    padding-right: 0.5em;
}
.variable .name:after {
    font-weight: bold;
    content : ":";
    padding-right: 0.5em;
}
.variable .value, .testcase-output .value {
    padding: 0.2em 1em 0.2em 0em;
    display: table-cell;
}
ol.testcases {
    padding: 0px;
    counter-reset: test_number -1;
}
ol.testcases > li {
    list-style:none;
}
ol.testcases > li:before {
    counter-increment:test_number;
    display: block;
    clear: both;
    content:counter(test_number) ")";
    color: inherit;
    background: inherit;
}

/* Problem Definition */
.problem-definition, .problem-limits {
    padding-left: 1.25em;
}
.problem-definition-lines, .limit-lines {
    display: table;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-left: 0px;
}
.definition-line, .limit-line {
    display: table-row;
    height: 1.5em;
    overflow: auto;
}
.limit-name:after {
    content: ":";
    margin-right: 1em;
}
.definition-name, .definition-value, .limit-name, .limit-value {
    display: table-cell;
}
.definition-value {
    padding-left: 0.5em;
}
.definition-name:after {
    content: ":";
}
#contest-division:before {
    content: "Div ";
}
#problem-score:before {
    content: "- Problem ";
}
#problem-name {
    display: block;
}

/* Tags, hidden default */
.tag {
    visibility: hidden;
    position: absolute;
}

        body {
    /* font color */
    color: #333333;
    /* background color */
    background-color: white;
}
.section .section-title {
    /* title color */
    color: black;
}
li.testcase .data {
    /* highlight color */
    background: #eee;
}

    </style>
    
    
    

</head>

<body>
    <h1 class="heading">
        <span id='contest-name'>SRM 144</span>
        <span id='contest-division'>2</span>
        <span id='problem-score'>550</span>
        <span id='problem-name'>BinaryCode</span>
    </h1>

    <hr />

    <!-- Problem Statement -->
    <div class="section">
        <h2 class="section-title">Problem Statement</h2>
        <div class="problem-intro">
            <intro escaped="1"><p>Let's say you have a binary string such as the following:</p>

<p><tt>011100011</tt></p>

<p>One way to encrypt this string is to add to each digit the sum of its adjacent digits.  For example, the above string would become:</p>

<p><tt>123210122</tt></p>

<p>In particular, if <tt>P</tt> is the original string, and <tt>Q</tt> is the encrypted string, then <tt>Q[i] = P[i-1] + P[i] + P[i+1]</tt> for all digit positions <tt>i</tt>.  Characters off the left and right edges of the string are treated as zeroes.</p>

<p>An encrypted string given to you in this format can be decoded as follows (using <tt>123210122</tt> as an example):

<ol><li>Assume <tt>P[0] = 0</tt>.</li>
<li>Because <tt>Q[0] = P[0] + P[1] = 0 + P[1] = 1</tt>, we know that <tt>P[1] = 1</tt>.</li>
<li>Because <tt>Q[1] = P[0] + P[1] + P[2] = 0 + 1 + P[2] = 2</tt>, we know that <tt>P[2] = 1</tt>.</li>
<li>Because <tt>Q[2] = P[1] + P[2] + P[3] = 1 + 1 + P[3] = 3</tt>, we know that <tt>P[3] = 1</tt>.</li>
<li>Repeating these steps gives us <tt>P[4] = 0</tt>, <tt>P[5] = 0</tt>, <tt>P[6] = 0</tt>, <tt>P[7] = 1</tt>, and <tt>P[8] = 1</tt>.</li>
<li>We check our work by noting that <tt>Q[8] = P[7] + P[8] = 1 + 1 = 2</tt>.  Since this equation works out, we are finished, and we have recovered one possible original string.</li></ol></p>

<p>Now we repeat the process, assuming the opposite about <tt>P[0]</tt>:

<ol><li>Assume <tt>P[0] = 1</tt>.</li>
<li>Because <tt>Q[0] = P[0] + P[1] = 1 + P[1] = 1</tt>, we know that <tt>P[1] = 0</tt>.</li>
<li>Because <tt>Q[1] = P[0] + P[1] + P[2] = 1 + 0 + P[2] = 2</tt>, we know that <tt>P[2] = 1</tt>.</li>
<li>Now note that <tt>Q[2] = P[1] + P[2] + P[3] = 0 + 1 + P[3] = 3</tt>, which leads us to the conclusion that <tt>P[3] = 2</tt>.  However, this violates the fact that each character in the original string must be '0' or '1'.  Therefore, there exists no such original string <tt>P</tt> where the first digit is '1'.</li></ol></p>

<p>Note that this algorithm produces at most two decodings for any given encrypted string.  There can never be more than one possible way to decode a string once the first binary digit is set.</p>

<p>Given a <type>String</type> <b>message</b>, containing the encrypted string, return a <type>String[]</type> with exactly two elements.  The first element should contain the decrypted string assuming the first character is '0'; the second element should assume the first character is '1'.  If one of the tests fails, return the string &quot;NONE&quot; in its place.  For the above example, you should return <tt>{&quot;011100011&quot;, &quot;NONE&quot;}</tt>.</p></intro>
        </div>
    </div>
    
    <!-- Problem definition -->
    
    <div class="section" id="definition">
        <h2 class="section-title">Definition</h2>
        <div class="problem-definition">
            <ul class="problem-definition-lines">
                <li class="definition-line" id='class-line'>
                    <span class='definition-name'>Class</span>
                    <span class='definition-value'>BinaryCode</span>
                </li>
                <li class="definition-line" id='method-line'>
                    <span class='definition-name'>Method</span>
                    <span class='definition-value'>decode</span>
                </li>
                <li class="definition-line" id='parameters-line'>
                    <span class='definition-name'>Parameters</span>
                    <span class='definition-value'>
                    
                        string
                    
                    </span>
                </li>
                <li class="definition-line" id='returns-line'>
                    <span class='definition-name'>Returns</span>
                    <span class='definition-value'>
                        tuple(string)
                    </span>
                </li>
                <li class="definition-line" id='signature-line'>
                    <span class='definition-name'>Method signature</span>
                    <span class='definition-value'>
                        def decode(self, message)
                    </span>
                </li>
            </ul>
            <div class="problem-definition-public-tip">(be sure your method is public)</div>
        </div>        
    </div>
    

    <!-- Limits -->
    <div class="section">
        <h2 class="section-title">Limits</h2>
        <div class='problem-limits'>
            <ul class="limit-lines">
                <li class='limit-line'>
                    <span class='limit-name'>Time limit (s)</span>
                    <span class='limit-value'>2.000</span>
                </li>
                <li class='limit-line'>
                    <span class='limit-name'>Memory limit (MB)</span>
                    <span class='limit-value'>64</span>
                </li>
            </ul>
        </div>
    </div>

    
    
    <!-- Constraints -->
    <div class="section">
        <h2 class="section-title">Constraints</h2>
        <ul class="constraints">
        
            <li><user-constraint escaped="1"><b>message</b> will contain between 1 and 50 characters, inclusive.</user-constraint></li>
        
            <li><user-constraint escaped="1">Each character in <b>message</b> will be either '0', '1', '2', or '3'.</user-constraint></li>
        
        </ul>
    </div>

    <!-- Test cases -->
    <div class="section">
        <h2 class="section-title">Test cases</h2>
        <ol class="testcases" start='0'>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">message</span>
                                <span class="value data">
                                
                                    &quot;123210122&quot;
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            { &quot;011100011&quot;, &quot;NONE&quot; }
                        
                        </span>
                    </div>
                    
                    <div class="testcase-annotation">
                        <div class='tag'>note</div>
                        <div class="testcase-comment"><p>The example from above.</p></div>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">message</span>
                                <span class="value data">
                                
                                    &quot;11&quot;
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            {&quot;01&quot;,<br />&nbsp;&quot;10&quot;}
                        
                        </span>
                    </div>
                    
                    <div class="testcase-annotation">
                        <div class='tag'>note</div>
                        <div class="testcase-comment"><p>We know that one of the digits must be '1', and the other must be '0'.  We return both cases.</p></div>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">message</span>
                                <span class="value data">
                                
                                    &quot;22111&quot;
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            { &quot;NONE&quot;, &quot;11001&quot; }
                        
                        </span>
                    </div>
                    
                    <div class="testcase-annotation">
                        <div class='tag'>note</div>
                        <div class="testcase-comment"><p>Since the first digit of the encrypted string is '2', the first two digits of the original string must be '1'.  Our test fails when we try to assume that <tt>P[0] = 0</tt>.</p></div>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">message</span>
                                <span class="value data">
                                
                                    &quot;123210120&quot;
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            {&quot;NONE&quot;,<br />&nbsp;&quot;NONE&quot;}
                        
                        </span>
                    </div>
                    
                    <div class="testcase-annotation">
                        <div class='tag'>note</div>
                        <div class="testcase-comment"><p>This is the same as the first example, but the rightmost digit has been changed to something inconsistent with the rest of the original string.  No solutions are possible.</p></div>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">message</span>
                                <span class="value data">
                                
                                    &quot;3&quot;
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            {&quot;NONE&quot;,<br />&nbsp;&quot;NONE&quot;}
                        
                        </span>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">message</span>
                                <span class="value data">
                                
                                    &quot;12221112222221112221111111112221111&quot;
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            {&quot;01101001101101001101001001001101001&quot;,<br />&nbsp;&quot;10110010110110010110010010010110010&quot;}
                        
                        </span>
                    </div>
                    
               
                </div>
            </li>
            
        </ol>
    </div>
    <hr />

    This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
</body>
</html>
